Skip to main content

Full text of "Characterising planar Cayley graphs and Cayley complexes in terms of group presentations"

See other formats


A group has a flat Cayley complex if and only if 
it has a VAP-free Cayley graph 



Agelos Georgakopoulos* 

Technische Universitat Graz 
Steyrergasse 30, 8010 
Graz, Austria 



Abstract 

We prove that a Cayley graph can be embedded in the euclidean plane 
without accumulation points of vertices if and only if it is the 1-skeleton 
of a Cayley complex that can be embedded in the plane after removing 
some redundant simplices. 



1 Introduction 

The study of groups that have Cayley graphs embeddable in the euclidean plane 
R 2 , called planar groups, has a tradition starting in 1896 with Maschke's charac- 
terization of the finite ones. Among the infinite planar groups, those that admit 
a flat Cayley complex, defined below, have received a lot of attention. They are 
important in complex analysis as they include the discontinuous groups of mo- 
tions of the euclidean and hyperbolic plane. Moreover, they are closely related 
to the surface groups [HJ Section 4.10]. These groups are now well understood 
due to the work of Macbeath [T3], Wiikie [T7], and others; see [IB] for a survejOJ 
Planar groups that have no flat Cayley complex are harder to analyse, and they 
are the subject of on-going research [31 El El 13 [H] - 

The assertion of the title can probably be derived from the results of [IB] . 
The aim of this paper is firstly, to provide an elementary proof of this assertion, 
avoiding the heavy machinery used in [18) , and secondly, to refine the assertion 
into a theorem about planar Cayley graphs, not just their groups: 

Theorem 1.1. A planar Cayley graph of a group T is VAP-free if and only if 
it is the 1-skeleton of a flat Cayley complex ofT. 

A planar graph is said to be Vertex- Accumulation- Point- free, or VAP-free 
for short, if it has an embedding in R 2 such that the images of its vertices have 
no accumulation point. The study of a planar graph is often simplified if one 
knows that the graph is VAP-free; examples range from structural graph-theory 
[3] to percolation theory [TJ] and the study of spectral properties [H] . A further 



♦Supported by FWF grant P-19115-N18. 

1 In |18l the term Cayley complex is not used but it is implicit in Theorems 4.5.6 and 6.4.7 
that a group admits a flat Cayley complex if and only if it is a planar discontinuous group. 



1 



example is Thomassen's Theorem 12.31 below, which becomes false in the non- 
VAP-free case. VAP-free graphs can be characterized by a condition similar 
to that of Kuratowski's; see [5]. VAP-free embeddings also appear with other 
names in the literature, most notably "locally finite" ' . 

The Cayley complex A" of a group presentation P = (S, R) is the universal 
cover of its presentation complex, see [10) . From this we derive the simplified 
Cayley complex of P as follows. Firstly, for every pair of parallel edges e, e', 
resulting from an involution in 5, we identify e with e', glueing them together 
according to a homeomorphism from e to e! that maps each endvertex to itself. 
We remove any 2-simplices of X that were bounded by the circle e U e'; all 
other 2-simplices incident with e or e' are preserved. In the resulting 2-complcx 
A', we define two 2-simplices to be equivalent if they have the same boundary. 
Removing all but one of the elements of each equivalence class from A' we 
obtain the simplified Cayley complex of P. 

Equivalently, we can define the simplified Cayley complex of P = (S, R) by 
building the corresponding Cayley graph, identifying each pair of parallel edges 
into a single edge, and then for every cycle C of this graph induced by a relator 
in R, introducing a 2-simplcx having C as its boundary. 

We say that a Cayley complex is flat if the corresponding simplified Cayley 
complex is planar, that is, it admits an embedding into R 2 . 

For example, the Cayley complex of the group presentation (a | a") has 
n equivalent 2-simplices, while the corresponding simplified Cayley complex 
has only one, and is planar. As a further example, consider the presentation 
(a, b | b 2 , a6a _1 6). The corresponding simplified Cayley complex is a 2-way in- 
finite ladder with each 4-gon bounding a 2-simplex; note that this complex is 
planar, while the usual Cayley complex is not. These two examples show that 
the above simplifications of the Cayley complex are necessary to make Theo- 
rem 11.11 true. 

We prove Theorem 11.11 in the next section. In Section [3] we examine VAP- 
freeness as a group-theoretical invariant. Finally, in Section @] we show how 
VAP-freeness can be recognised in a group presentation. 

We will follow the terminology of [3] for graph-theoretical terms and that of 
[TJ [TU] for group-theoretical ones. 

2 Proof of main result 

One of our main tools will be the (finitary) cycle space C/(G) of a graph G = 
(V,E), which is defined as the vector space over Z2 consisting of those subsets 
of E such that can be written as a sum (modulo 2) of a finite set of circuits, 
where a set of edges D C E is called a circuit if it is the edge set of a cycle of 
G. Thus Cf(G) is isomorphic to the first simplicial homology group of G over 
Z2 . The circuit of a closed walk W is the set of edges traversed by W an even 
number of times. Note that the direction of the edges is ignored when defining 
circuits and C/(G). 

In this section we will be assuming that our graphs have no parallel edges. 
In a Cayley graph this can be achieved by drawing, for every involution in the 
generating set, a single undirected edge rather than a pair of parallel edges 
with opposite directions. This convention affects neither planarity nor VAP- 
freeness, and so our assumption comes without loss of generality for the proof 



2 



of Theorem HHJ 

Our first lemma, a well-known fact which is easy to prove, relates C/(G) to 
group presentations. We will say that a closed walk W in G is induced by a 
relator R, if W can be obtained by starting at some vertex g and following the 
edges corresponding to the letters in R in order; note that for a given R there 
are several walks in G induced by R, one for each starting vertex g S V(G). 

Lemma 2.1. Let G = Cay(T,S) be a Cayley graph of the group T, and let 
(S | R) be a presentation ofT. Then the set of edge-sets of walks in G induced 
by relators in R generates C/(G). 

Conversely, if R' is a set of relations of T with letters in a generating set 
S such that the set of cycles of Cay(T, S) induced by R' generates C/(G), then 
(S | R'} is a presentation ofY. 

Combined with the next easy fact, this allows one to deduce group presen- 
tations from VAP-free embeddings of a Cayley graph. 

Lemma 2.2. Let G be a VAP-free plane graph. Then the set of finite face 
boundaries of G generates C/(G). 

Proof. It suffices to show that the edge-set of every cycle C of G is a sum of 
edge-sets of finite face boundaries. This is indeed the case, for as G is VAP-free 
there must be a side A of C containing only finitely many vertices, and so E(C) 
is the sum of the edge-sets of the face boundaries lying in A. □ 

The following theorem of Thomasscn generalises MacLane's classical pla- 
narity criterion [3l Theorem 4.5.1] to infinite VAP-free planar graphs. It will 
easily imply the backward implication of Theorem 11.11 A 2-basis of G is a 
generating set B of C/(G) such that no edge of G appears in more than two 
elements of B. 

Theorem 2.3 f [15l Section 7]). A connected graph G has a 2-basis if and only 
if it is planar and has a VAP-free embedding. 

The following fact is probably known to experts in the study of infinite 
vertex transitive graphs. We include a proof sketch for the convenience of the 
non-expert. A double-ray is a 2-way infinite path (with no repetition of vertices). 

Lemma 2.4. Let G be an infinite, connected, vertex transitive graph which is 
not a double-ray. Then for every pair of vertices x, y of G, no component of 
G — {x, y} is finite. 

Proof. To begin with, it is easy to prove that 

for every x 6 V(G), no component of G — {x} is finite, (1) 

by considering a minimal such component C and mapping x to some vertex of 
C. 

Suppose that some component C of G — {x, y} is finite, and choose x, y so 
as to minimise |F(G)|. We claim that the graph C has no cut- vertex. Indeed, if 
z G V(C) separates C, then G—{x, z} contains a component properly contained 
in C, contradicting the minimality of the latter. Moreover, each of x, y has at 
least two neighbours in C; for if y has a single neighbour y' in C, then we 



3 



could have replaced y by y' to obtain a separator {x, y'} cutting off a smaller 
component, and if y has no neighbour in C then ([T]) is contradicted. These two 
observations, combined with Menger's theorem [3J Theorem 3.3.1], imply that 
there are two independent x-y paths P, Q through C. Moreover, (at least) one 
of x, y, say x, is contained in an infinite subgraph A that does not meet P, Q 
except at x. 

Let z € V(C), and consider an automorphism g mapping x to z. Then, 
there is a vertex w — gy such that {z, w} separates G. We consider three cases. 

If w lies in a component C ^ C of G — {x, y}, then each of gP, gQ, gX meets 
both C" and C. But this is impossible since C is separated from C by x, y and 
the only vertices meeting more than one of gP, gQ, gX are z and w. 

If ui lies in C, then some component of G — {z, w} is properly contained in 
C contradicting its minimality. 

Finally, if w = y, then as the component gC of G — {z, w} cannot be smaller 
than C, it must contain the vertex x. Note that x is incident with an infinite 
component C of G — {x,y} because otherwise y contradicts ([T]). But then gC 
contains C", contradicting the fact that its translate C is finite. 

Thus, in all three cases we obtained a contradiction. This proves Lemma 12^1 

□ 

We can now prove our main result. 

Proof of Theorem \l.ll For the forward implication, let G be a planar Cayley 
graph of the group T, with respect to the generating set <S, admitting a VAP- 
free embedding o. By Lemma 12.51 below, if F is a finite face boundary in er, 
then every translate of F is a face boundary. This means that if we let TV 
be the set of relations corresponding to the finite face boundaries of a incident 
with the group identity e, then every finite face boundary of a is induced by 
some element of TV , and conversely any cycle induced by some element of TV 
bounds a face in a. By Lemmas 12.11 and 12.21 (S \ TV) is a presentation of T. 
The corresponding simplified Cayley complex is planar and VAP-free since we 
can embed its 1-skclcton G by a and then every 2-simplcx can be embedded 
into the face of a bounded by the corresponding cycle. 

The backward implication follows easily from Thcorcm l2.3l let A be a planar 
simplified Cayley complex and let G be its 1-skelcton. Let B 1 be the set of 
closed walks in G bounding a 2-simplcx of A — in fact, these closed walks 
are cycles since A is planar — and let B := {E(C) \ C G B'} be the set 
of the corresponding edge-sets. Note that B generates C/(G) by Lemma [2.11 
Moreover, since A is planar, no edge of A lies in the boundary of more than 
two 2-simplices. Thus B is a 2-basis of G, and so Theorem 12.31 implies that G is 
VAP-free. □ 

Lemma 2.5. Let G be an infinite vertex transitive graph with a VAP-free em- 
bedding o . If F is a finite face boundary in a then every image of F under any 
automorphism of G is a face boundary in a. 

Proof. Suppose to the contrary that some image F' — gF of F under an auto- 
morphism g is not a face boundary. Then, as o is VAP-free, one of the sides of 
F' contains at least one finite component C. Let N(C) be the set of vertices of 
F' sending an edge to C. Then F' — N(C) consists of a set of disjoint paths, 



4 



which we call the intervals. Note that there are at least three intervals, for if 
|7V(C) < 2 then Lemma \2. 41 is contradicted. 
We claim that 

no component of G — F' sends edges to more than one interval. (2) 

Indeed, if such a component C existed, then, by a topological argument, it 
would be impossible to embed G is such a way that both C and C lie in the 
same side of F' (Figured]), but such an embedding must be possible since F is 
a face boundary. 

Next, we claim that at most one of the intervals sends an edge to an infinite 
component of G — F 1 . For if there are intervals I ^ J adjacent with infinite 
components Cj, Cj of G — F' , then replacing I in F' by a path through C we 
would obtain a cycle D that separates Ci from Cj by @ (Figure [TJ . But then 
g~ 1 /, .g~ 1 J must lie in distinct sides of g~ x F> since F = g~ x F' and F is a face 
boundary, contradicting the fact that a is VAP-frcc. 




Figure 1: A contradictory situation in the proof of Lemma [2.51 

Thus our claim is proved, implying that there is a unique interval I adjacent 
with the infinite component of G—F'. This fact, combined with ©, implies that 
deleting the vertices x, y € N(C) bounding / leaves a finite component, namely 
the component of G— {x, y} containing C. But this contradicts Lemma [2^41 □ 

3 VAP-freeness as a group-theoretical invariant 

A planar group can admit both VAP-free and non-VAP-free Cayley graphs. For 
example, the Cayley graph corresponding to the presentation (a, b \ b 2 ,abati), 
of the infinite dihedral group, is VAP-free planar, but adding the redundant 
generator c — ab keeps the Cayley graph planar and makes it non-VAP-free 
as the reader can check. Thus VAP-freeness is not group-theoretical invariant 
in general. However, it becomes an invariant if one only considers 3-connected 
Cayley graphs: 

Theorem 3.1. If a group T has a 3-connected VAP-free planar Cayley graph 
and a group A has a 3-connected non-VAP-free planar Cayley graph, then T is 
not isomorphic to A. 

Before proving this let us see a further example showing that it is necessary 
that both graphs in the assertion be 3-connected. Consider the Cayley graph 



5 



corresponding to the presentation (a, b | a 4 ,6 4 ). This is a free product of 4- 
cycles, and it is easy to see that it has a VAP-free embedding and that its 
connectivity is 1. Now add the redundant generators c = ab and d = a 2 b 2 a 2 . 
Note that d 2 = 1. Figure [2] shows that the corresponding Cayley graph is still 
planar, and it is easy to check that it is 3-connected. The given embedding is 
not VAP-free. It now follows easily from the following classical result, proved 
by Whitney [TH Theorem 11] for finite graphs and by Imrich (TTJ for infinite 
ones, that no embedding of this graph is VAP-free. 




Theorem 3.2. Let G be a 3-connected graph embedded in the plane. Then every 
automorphism of G maps each facial path to a facial path. 

We will need a few lemmas for the proof of Theorem 13.11 

Lemma 3.3. Let G be a 2-connected planar graph and let oj, ip be distinct ends 
of G. Then there is a cycle C in G that separates oj from ip, i.e. every double-ray 
with a tail in uj and a tail ip has a vertex in C . 

Proof. Fix an embedding a of G. Consider a finite set of vertices S = {s± , S2 , . . . , Sfc} 
separating oj from ip, and let C\ be a cycle containing s\, S2', such a cycle exists 
since G is 2-connected. If C\ does not separate oj from ip then both ends lie 
in one of the sides of C±, the outside say. Note that some vertex of 5* must 
also lie outside C\, for otherwise every double-ray with a tail in u> and a tail ip 
would have to go through C\ to meet S, contradicting the fact that C\ does not 
separate oj from ip. So pick the least index j such that Sj lies outside C\. Now 
consider two independent paths P\ , P2 from Sj to C\ , and let A be the region 
of R 2 \{Ci U P\ U P2] containing rays in oj. The boundary of A is a cycle C2 
containing P1UP2 and a subpath of C\. Note that no element of {si, S2, • • • , Sj} 
lies in A because those points do not lie outside C\ . Repeating this argument we 
construct the sequence of cycles C\, C2, ■ ■ ■ , C m , terminating with a cycle C m 
such that the outside of C m contains ui but none of the Si . This cycle separates 
uj from ip because every double-ray with a tail in w and a tail ip has to cross it 
to meet S. □ 

Using this we can prove: 

Lemma 3.4. Let G be a 2-connected graph with a VAP-free embedding a and 
more than 1 end. Then at least one of the faces of a has infinite boundary. 



G 



Proof. By Lemma |3~B1 there is a cycle C separating two ends u>, ip of G. Since a 
is VAP-free, both these ends lie in the same side of C, the outside say Let K u 
(respectively K^) be the component of G — C containing rays in w (resp. ip). 
Easily, it is possible to find independent subpaths P w , P/, of C such that every 
vertex of C adjacent with lies in P u , and similarly for and P^. Let x 
be an endvertex of P w ; without loss of generality, x is adjacent with K u . 

By the choice of x we can choose an edge e = xy with y 6 V(K U ) and a 
further edge f = xz incident with x with z not in K u and / not in P w , so that 
e, / lie on a common face boundary F . Now if F is infinite we are done, so 
suppose it is finite. Consider the path F' := F — C. One of the endvertices of 
F' is x by construction, and the other endvertex x' must also lie on P u since F' 
must be contained in K^UC. Now consider the cycle D contained in P'UP U . By 
construction, _fT w , lie in distinct sides of D. This contradicts our assumption 
that a is VAP-free. □ 

Our last lemma is 

Lemma 3.5. There is no 3-connected vertex-transitive VAP-free planar graph 
with more than 1 end. 

Proof. If such a graph G exists, then by Lemma 13.41 it has an infinite face- 
boundary. By Theorem 13.21 this implies that every vertex of G is incident with 
an infinite face-boundary. 

Thus we can pick two vertices x, y that lie in a common double ray R of G 
contained in a face-boundary. As G is 3-connected, there are three independent 
x-y paths Pi, P2, P3 by Menger's theorem [21 Theorem 3.3.1]. By an easy topo- 
logical argument, there must be a pair of those paths, say Pi,P2, whose union 
is a cycle C such that some side of C contains a tail of R and the other side 
of C contains P3. We may assume without loss of generality that P3 is not a 
single edge, for we are allowed to choose x and y far apart. Thus the side of 
C containing P3 contains at least one vertex z. By our previous remarks, z is 
incident with an infinite face-boundary. This means that both sides of C contain 
infinitely many vertices, contradicting our assumption that G is VAP-free. □ 

We can now prove the main result of this section. 

Proof of Theorem VS. 1\ If any of T, A is 1-cndcd then we are done since it is well- 
known, and not hard to prove, that all its planar Cayley graphs are VAP-free 
in this case. The result now follows immediately from Lemma 13.51 □ 

4 VAP-free presentations via MacLane's planarity 
criterion 

In this section we derive a further characterisation of the groups that admit a 
flat Cayley complex by means of group presentations. We achieve this using 
Thomassen's Theorem 12.31 

Define a VAP-free presentation to be a group presentation {S \ 1Z) with the 
following two properties. First, every closed walk induced by a relator R £ 1Z is 
a cycle; in other words, no proper subword of R is a relation. Second, for every 
edge e in the corresponding Cayley graph G, at most two cycles of G induced 



7 



by the relators in 1Z contain e. Note that the latter property can be checked by 
an easy algorithm once the former is guaranteed. 

By Lemma I!Q1 the cycles induced by the relators of a VAP-free presentation 
form a 2-basis. Combined with Theorem 12.31 this yields the following valuable 
tool, which in many cases [7] allows one to deduce that certain Cayley graphs 
are planar by looking only at the corresponding presentations. 

Corollary 4.1. A group admits a flat Cayley complex, and a VAP-free Cayley 
graph, if and only if it admits a VAP-free presentation. 

Proof. Given a planar simplified Cayley complex of the group T it is straight- 
forward to derive a VAP-free presentation of T. By the above discussion, such 
a presentation yields a VAP-free Cayley graph of T. This in turn implies that 
r admits a planar simplified Cayley complex by Theorem ll.il □ 

The fact that a group with a planar simplified Cayley complex admits a 
VAP-free presentation is implicit in [18l Theorem 4.5.6]. 

In fact, we can say a bit more. Thomassen |15l Theorem 7.4.] also proved 
that if G is 2-connccted, then Theorem 12.31 can be strengthened to yield that 
given any 2-basis B of G, there is a VAP-free embedding a of G such that 
B is the set of finite face-boundaries of a. If G is a Cayley graph then the 
requirement of being 2-connectcd can be dropped by applying the result to the 
maximal 2-connected subgraphs of G, which must be either Cayley graphs too 
or single edges corresponding to free generators. Thus we have 

Corollary 4.2. Given a VAP-free presentation, the corresponding Cayley graph 
has a VAP-free embedding the finite face-boundaries of which are precisely the 
cycles of G induced by the relators. 

Acknowledgements 

I am grateful to Martin Dunwoody for pointing out a shortcoming of an earlier 
version of the paper. 

References 

[1] O. Bogopolski. Introduction to Group Theory. EMS, Zucrich, Switzerland, 
2008. 

[2] Q. Cui, J. Wang, and X. Yu. Hamilton circles in infinite planar graphs. 
J. Combm. Theory (Series B), 99(1):110-138, 2009. 

[3] R. Diestel. Graph Theory (4th edition). Springer- Vcrlag, 2010. 

[4] C. Droms. Infinite-ended groups with planar Cayley graphs. J. Group 
Theory, 9(4):487-496, 2006. 

[5] C. Droms, B. Servatius, and H. Scrvatius. Connectivity and planarity of 
Cayley graphs. Beitr. Algebra Geom., 39(2):269-282, 1998. 

[6] M.J. Dunwoody. Planar graphs and covers. Preprint. 



8 



[7] A. Gcorgakopoulos. The planar cubic cayley graphs. Preprint 2011. 

[8] A. Gcorgakopoulos. The planar cubic cayley graphs of connectivity 2. 
Preprint. 

[9] R. Halin. Zur haufungspunktfreien darstellung abzahlbarer graphen in der 
ebene. Archiv der Mathematik, 17:239-243, 1966. 

[10] A. Hatcher. Algebraic Topology. Cambrigdc Univ. Press, 2002. 

[11] W. Imrich. On Whitney's theorem on the unique embeddability of 3- 
connected planar graphs. In Recent Adv. Graph Theory, Proc. Symp. 
Prague 1974, pages 303-306. 1975. 

[12] M. Keller. Curvature, geometry and spectral properties of planar graphs. 
Preprint. 

[13] G. Kozma. Percolation, perimetry, planarity. Rev. Mat. Iberoamericana, 
23(2):671-676, 2007. 

[14] A.M. Macbeath. The classification of non-euclidean plane crystallographic 
groups. Can. J. Math., 19:1192-1205, 1967. 

[15] C. Thomassen. Planarity and duality of finite and infinite graphs. J. Corn- 
bin. Theory (Series B), 29(2):244 - 271, 1980. 

[16] H. Whitney. Congruent graphs and the connectivity of graphs. American 
J. of Mathematics, 54(1):150-168, January 1932. 

[17] H.C. Wilkic. On non-Euclidean crystallographic groups. Math. Z., 91:87- 
102, 1965. 

[18] H. Zieschang, E. Vogt, and H.-D. Coldewey. Surfaces and planar discontin- 
uous groups. Revised and expanded transl. from the German by J. Stillwell. 
Lecture Notes in Mathematics 835. Springer- Verlag, 1980. 



9